1. Field of the Invention
This invention relates in general to the field of arithmetic units within microprocessors, and more specifically to a method and apparatus for improved execution of sequential multiply instructions using recoding logic.
2. Description of the Related Art
A primary function of microprocessors is to perform a large number of mathematical operations as fast as possible. The mathematical operations within a microprocessor are typically performed by an arithmetic logic unit (ALU). More specifically, data is provided to the ALU in the form of operands that are either stored within the microprocessor, or are retrieved from memory. The operands are manipulated by the ALU in response to an instruction, and a result is provided as an output. The result is then either held in the microprocessor, to be used for subsequent operations, or is stored back into memory. The microprocessor continually reads new operands, associated with new instructions, operates on these operands, and produces a result.
One mathematical operation that has required significant processing time is that of multiplication. A multiply instruction specifies two operands to be multiplied together, to produce a product. One of the operands is called the multiplier, the other operand is called the multiplicand.
Within an arithmetic unit, it is typical for a multiplication to be performed using a process of iterative add/shift operations. As will be further described in the Detailed Description below, the multiplicand is added/shifted depending on the contents of the multiplier.
A problem with the iterative add/shift process is that a microprocessor time interval is typically required for each bit in the multiplier. Thus, if a multiplier is a 32-bit value, at least 32 time intervals are required to perform the multiplication.
An improvement in microprocessor multiplication has been obtained by using recoding logic to reduce the number of iterations required for a multiply. The recoding logic implements a particular algorithm designed to optimize multiplication within an arithmetic unit. One such algorithm is that of Andrew Booth, discussed below, and is termed the Booth algorithm. Implementation of recoding logic using Booth's algorithm is ubiquitous within microprocessor arithmetic units. For a recent example, see U.S. Pat. No. 5,638,313 entitled "BOOTH MULTIPLIER WITH HIGH SPEED OUTPUT CIRCUITRY", by Chu, which is hereby incorporated by reference.
The recoding logic is typically provided with a multiplier operand that sets up the recoding logic to control a sequence of add/shift operations executed on a multiplicand. However, all known recoding logic requires a non zero setup time, after receiving the multiplier, before it can begin controlling the add/shift operations on the multiplicand. This setup time creates processing delays during a multiply instruction.
The setup time is particularly cumbersome when a multiply instruction specifies that its multiplier is the product of a previous multiply instruction. Until the product of the previous multiply instruction has been calculated, and the product is provided to the recoding logic, the recoding logic cannot be setup to perform the subsequent multiply. This additional delay in setting up the recoding logic, when an operand dependency is specified by a multiply instruction, adds additional processing delay. Such delay, resulting from setting up the recoding logic with the product of a previous multiply, is undesirable.
Therefore, what is needed is a method and apparatus that allows operand dependencies in sequential multiply operations to be detected, and the setup time for the recoding logic, typically associated with such dependencies, to be eliminated.